/*
题目：实现 strStr()
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 */
public class StrStr {
    public int[] getNext(String sub) {
        int i = 1;
        int k = -1;
        int len = sub.length();
        int[] next = new int[len];  //next数组是基于子字符串创建的
        next[0] = -1;
        while (i < len) {
            if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) {//现在的值和回溯后的值相等
                next[i++] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
    public int Kmp(String str, String sub) {
        int[] next = getNext(sub);
        int i = 0;//遍历str
        int j = 0;//遍历sub
        int strLen = str.length();
        int subLen = sub.length();
        while (i < strLen && j < subLen) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= subLen) {
            return i - j;
        }
        return -1;

    }
    public int strStr(String haystack, String needle) {
        return Kmp(haystack,needle);
    }
}
